The present invention relates to zero knowledge protocols that allow the knowledge of some “secret” or private key information in a first party domain to be verified by a second party without imparting the actual secret information or private key to that second party or to any eavesdropping third party. In particular, the invention has application in the implementation of zero knowledge protocols in systems and devices that have restricted computational resource such as smart cards, mobile electronic devices and the like.
Throughout the present specification, the first party owning the secret information or private key (“s”) and wishing to prove that it has possession of the information will be referred to as the “prover” (“P”); the second party wishing to verify that this is the case without actually receiving knowledge of the secret will be referred to as the “verifier” (“V”). The prover P and verifier V may be any suitable electronic device. The secret information may be any numeric value, hereinafter referred to as the secret number of the prover P.
Zero knowledge protocols are very valuable tools that can be used for authentication of devices such as smart cards used in financial transactions, or in pay television access, and for identification of devices connecting to a network, such as mobile telephones and other electronic devices.
Conventionally, the prover will offer a computationally difficult mathematical problem, and the verifier will ask for one of the two or more possible solutions to the problem. If the prover knows critical information relating to the solution, it is able to provide either (or any) of the requested available solutions on demand, according to the request of the verifier. If the prover does not know the critical information, it is computationally infeasible for it to always be able to provide the requested solution to the verifier.
Usually, zero knowledge protocols rely on some hard mathematical problems such as the factorisation of integers or the discrete logarithm problem. A drawback to these protocols is that they usually require extensive use of modular arithmetic which require greater computational resource than is desirable for lower power, limited capacity devices such as smart cards and portable electronic devices. Thus, a typical implementation time for the security protocols is greater than desirable.